1. Field of the Invention
The present invention relates to a variable length coding method, a variable length decoding method, and apparatuses therefor, and more particularly, to a variable length coding method and a variable length decoding method, in which a plurality of mapping tables are used so that the advantages of a universal variable length code table can be maintained and efficiency lowering of compression coding can be prevented, and apparatuses therefor. The present application is based on Korean Application No. 2000-26274, filed May 17, 2000, which is incorporated herein by reference.
2. Description of the Related Art
At present, the International Telecommunication Union Telecommunication Standardization Sector (ITU-T) has been working on an H.26L international standard related to the next generation of videophones. Although a series of moving picture coding methods related to videophones, such as H.261, H.263, H.263+, and later H.263++ and MPEG-4, were determined as ITU-T international standards, these international standards cannot meet newly appearing requirements. Therefore the H.26L standard is being prepared in order to cope with the new requirements. The new requirements are as follows.
The first requirement is for more improved coding efficiency and shorter end-to-end delay for ultra low-speed real-time applications. That is, it is a requirement for realizing a more enhanced frame rate than that of H.263+ base coding method at the same bit rate, and a requirement for realizing the picture quality obtained by using the H.263+ base coding method at a bit rate less than half the bit rate of the base coding method. The requirement is needed also from the aspect of coding delay. For example, the delay should be short enough to satisfy real-time interactive communication, and should be flexible enough to easily reduce delay time to less than a target delay time, at the cost of lowering picture quality if necessary. For future general usability, the second requirement is for complexity low enough to code/decode using only software. The third requirement is for an error tolerance and solidarity capable of coping with about 10−4 sporadic errors and about 10−3 crowding errors. Other new requirements include a requirement for a structure that is capable of easily coping with network environments, such as video streaming, a requirement for providing higher picture quality or entertainment quality of a main application at 8˜12 Kbps bit rate, a requirement for a scalability function of space, time, and SNR, a requirement for an intra coding function for random access of storage medium-based applications, a requirement for capability of reverse-direction prediction, etc. Particularly, in entropy coding of future low transmission coding, when a Huffman variable length coding method with a conventional Huffman coding table is used, the growing trend is wide use of a universal variable length coding table regardless of the types of coding data, in order to make the design simpler and clearer. This is to reduce the complexity of a processing method and apparatus caused by having a plurality of variable length coding tables, as in prior art. However, although the universal variable length coding table may reduce complexity of a processing method and apparatus, it causes a lower coding efficiency.
FIG. 1 illustrates the structure of a decoding apparatus using prior art.
A decoding unit 10 of FIG. 1 receives a coded bit stream (coded data), which is coded in a coding apparatus (not shown) and is formed of “0” and “1”. The decoding unit 10 divides each codeword from the received bit stream and then outputs code numbers, each corresponding to a distinct codeword. The method for dividing each codeword from the received bit stream will be explained later. A symbol extracting unit 11 receives a code number corresponding to each codeword and an element type signal for determining the kind of symbol, and outputs the corresponding symbol in the form of decoded data.
The decoding step of the decoding unit 10 will now be explained. The decoding unit 10 uses a universal variable length coding table (UVLC), and the UVLC is formed using the rule shown in FIG. 2. Here, Xn has a value of “0” or “1”. If information to be coded is INFO, it can be expressed as INFO=Xn . . . X1 X0. This INFO data is made to be a bit stream as shown in FIG. 2, in which every odd numbered bit is “0” except the last bit which is “1”. At this time, the length of the final codeword, which is made from INFO with insertion as shown in FIG. 2, is obtained by adding “1” to twice the number of bits of INFO, except when a code number is “0”. The codeword thus formed can be numbered in the direction of increasing length, and at this time, the number is referred to as a code number. An example is shown in FIG. 3. At this time, the relation between code number and INFO to be inserted can be expressed as the following equation 1:code_number=2L/2+INFO  (1)
Here, L is the length of a codeword, and as described above, the length is obtained by adding “1” to twice the length of INFO, except when a code number is “0”. In an example of the above rule, if a binary number “10” is provided as INFO, L is “5” and the code number is “5”.
Decoding can be very easily performed using this rule in reverse. That is, a UVLC table formed as described above has a predetermined characteristic in that an odd numbered bit of each codeword is always the binary number “0”, except for the last bit of each codeword which is always the binary number “1”. Therefore, the decoding apparatus 10 of FIG. 1 refers to odd numbered bits of an input bit stream, and if the binary number “1” is found, it can be determined that the bits up to the binary number “1” correspond to one codeword. After one codeword is found in this way, only even numbered bits in the found codeword are read, and those bits form a code number. This step is performed by the decoding apparatus 10 of FIG. 1.
If the decoding apparatus 10 of FIG. 1 outputs the code number, it needs to decode an actual symbol corresponding to the code number, that is, a symbol corresponding to the found INFO. Decoding is simply performed with reference to a table by a symbol extracting unit 11 of FIG. 1. That is, the symbol extracting unit 11 stores, for example, data as shown in FIG. 4. That is, if a code number and an element type (element_type), which indicates the kind of symbol, are received, the symbol extracting unit 11 outputs a symbol corresponding to the code number and the element type, and by doing so, performs decoding. Here, an example of element_type is MB-TYPE information which indicates the type of a macro block currently being decoded. As shown in FIG. 4, MB-TYPE information can be a skip type, which indicates substitution of video data of a corresponding location of a reference video for a motion vector, or can specify the size and form of a macro block, such as 16×16, 16×8, 8×16, 8×4, etc.
The conventional method described above has the following drawbacks. One kind of UVLC table is used for a plurality of symbols (for example, MT_TYPE, CBP(coded block pattern), . . . ). The compression efficiency of the variable length coding method is closely related to how well a codeword table is designed according to the probability distribution of symbols which are actually used. However, in the conventional method described above, although complexity in implementation is reduced by using a universal codeword table, code numbers and symbols are mapped to each other uniformly by a UVLC table, as shown in FIG. 4, regardless of the probability distribution of the actual symbols, and therefore the conventional method has a serious problem realizing the basic goal of maximum compression. That is, the UVLC table described above can be appropriate for certain kinds of symbols, but can cause lowered coding efficiency for other kinds of symbols. To solve this problem, a table optimized for each kind of symbol can be prepared to improve the efficiency, but in this case, the beneficial effects of the UVLC described above are sacrificed.